1. Field of the Invention
The present invention relates to search tree data structures.
2. State of the Art
In order to efficiently and quickly locate information within a data structure, elements within the data structure are often put in a particular order (i.e., sorted data structure) and an algorithm is employed to locate elements within the structure. The search is generally performed in a reiterative manner such that in a first interval (or iterative loop), the whole structure is searched, in the next interval a sub-set of the structure is searched, in the next interval, a sub-set of the previous sub-set is searched, and so on. Data structures are often sorted by keys, where a unique key is associated with each element within the data structure. For instance, to sort customer records alphabetically, the key is the last name, however, the other information, such as address, phone number, work number, do not matter in sorting the records alphabetically. In this case, the data structure is searched using the key (i.e., the last name) to obtain the data associated with each key (i.e., the address, etc.).
In a specific data structure, referred to as a binary search tree, the structure is made up of a plurality of nodes (FIG. 1). Keys in a binary search tree are binary numbers made-up of “1”s and “0”s. Stored at one type of node location are a binary key and two address pointers each pointing to a new node are stored. At another type of node location, a key and data (e.g., address, phone number, work number, etc.) is stored. A basic search of a binary search tree consists of comparing one or more bits of an input key to corresponding one or more bits of the data structure keys.
Hence, to search a binary search tree, in a first iteration the whole structure is searched. In the second iteration the search is halved and so on.
A binary search tree is a binary tree where every node's left subtree has values less than the nodes's value, and every right sub-tree has values greater. A new node is added as a leaf. A node is a unit of reference in a data structure, also called a vertex in graphs and trees. It is also a group of information which must be kept at a single memory location. A tree is a data structure accessed beginning at the root node. Each node is either a leaf or it is a parent which refers to child nodes. More formally, a connected forest. Contrary to a physical tree, the root is usually depicted at the top of the structure, and the leaves are depicted at the bottom. A root is the distinguished initial or fundamental item of a tree. The only item which has no parent. A parent is an item of a tree which refers to one or more child items which are conceptually on the next level “down” or farther from the root. A child is an item of a tree referred to by a parent item. Every item, except the root is the child of some parent. A leaf is a terminal or “bottom” item of a tree, i.e., an item with no child. More formally, a vertex with degree one.
Data structures may also be sorted by groups, referred to as radix sorting. For instance, in the above example in which the key is a “last name”, the data structure may be initially searched for the first letter of the key, such as the letter “Q”. This search would provide a pointer or index into a group of keys starting with “Q”. The next search might be of the second letter and so on.
A radix search using a binary key is performed by taking groups of bits of the binary key and comparing them to a corresponding number of bits of the key at each node. A radix 2 search compares one bit of the key at a time, radix 4 compares two bits at a time, a radix 16 compares four bits at a time.
The advantage of a binary search is that if you have a very sparse search and a large key (i.e., many bits), it works well/efficiently because each iteration of the search halves the total nodes to search. However, if the data structure includes a large number of nodes, it becomes more efficient to perform a radix search. Specifically, when performing a search, each search has an associated compare operation between the input key and the keys at each node. Each compare operation requires reading each 16-bit key from memory representing addition cycles for performing the search. For instance, if a 16-bit key is used to search a 400 node data structure (i.e., sparse search), fewer compares operations will be required, and hence comparing two 16-bit keys does not represent a large penalty to system operation. However, if the data structure is not sparse, for instance 64,000 nodes, the number of compares of a large key becomes computationally unwieldy.